From news-rocq.inria.fr!julienas!mcsun!howland.reston.ans.net!vixen.cso.uiuc.edu!newsrelay.iastate.edu!dunix.drake.edu!acad.drake.edu!pk6811s Mon Nov 15 15:42:29 1993
Article: 205 of rec.games.corewar
Newsgroups: rec.games.corewar
Path: news-rocq.inria.fr!julienas!mcsun!howland.reston.ans.net!vixen.cso.uiuc.edu!newsrelay.iastate.edu!dunix.drake.edu!acad.drake.edu!pk6811s
From: pk6811s@acad.drake.edu
Subject: '94 and the self-repair problem
Message-ID: <1993Nov14.235014.1@acad.drake.edu>
Lines: 127
Sender: news@dunix.drake.edu (USENET News System)
Nntp-Posting-Host: acad.drake.edu
Organization: Drake University, Des Moines, Iowa, USA
Date: Mon, 15 Nov 1993 05:50:14 GMT

In the interest of promoting the '94 standard, here is the code for a
self-repairing fighter 'bunker'.  It's not particularly successful,
but maybe illustrates some '94 possibilities.

First, I had the idea that a self-repairing program could be built
like 'paper', using multiple processes.  There would be a pair of
them, each keeping track of the other's code and repairing it if 
necessary.  Instead of using 'cmp' like the previous self-repairers
I wrote, this one would use 'add' or 'sub' to add the b-operands
of all the instructions and compare the total to an expected value.
If not equal, dat-bomb the damaged partner to kill off any spl-created
processes, then recopy the good code and start him again.

Speaking only '88 standard to start, I wrote an '88 version, and played
around with it for a while.  Using a graphical display (Redcoder) I
could watch it repairing code over and over when opposed by either
bombers or spl-jmp cmp-scanners.  Unfortunately it eventually succombed
to a rapid combination of hits on both partners, or to being overrun
by a djn-stream while in the process of repairing the other partner.
It became obvious that it needed to run much faster.

The limiting factor in speed is the length of code, since that is
also the number of processes needed in each partner.  I got to thinking
about what could be done with the '94 standard and thought I could
pare off 4 instructions under '94, which was almost true as I found out.

The program starts by copying the two partners into core, spaced 4000,
then starts both copies.  Each partner continually monitors the other
with this code:

    set      mov    initrp,rp
             sub.ba <rp,rp
    rpptr    jmn.a  rkill,rp
    ...
    initrp   dat    #0-2353,#re-rp+1+space

'rp' is a location in core that holds a pointer to the other partner's
code in its b-operand, AND the sum of partner's b-operands in its 
a-operand.  'set' initializes rp.  The 'sub.ba' subtracts partner's
b-operands from rp's a-operand which should result in zero.  If it's
not zero the program jumps to 'rkill'.  The advantage of '94 is being
able to load both the pointer and the value with a single mov instruction,
saving one line in the monitoring loop.

Here's the whole program:

;redcode-94
;name bunker
;kill bunker
;author P.Kline
;strategy self-repair pair [94]
space    equ 4000
boot     equ -500
rp       equ (re+2100)
copyf    dat #(re+1)
copyt1   dat #(re+1+space+boot)
copyt2   dat #(re+1+boot)

rb       dat    <2667,#space           ; pointer to partner
rkill    mov    re,>rb                 ; kill partner
         mov    rb,>rclr+200           ; wait for partner to die
         mov    <rb+space,<rb          ; restore partner
         spl    set+space,#5           ; start him (no zero b-operands allowed!)
         mov    rb,rb+space            ; correct partner's rb
set      mov    initrp,rp              ; initialize monitoring
         sub.ba <rp,rp                 ; check partner
rpptr    jmn.a  rkill,rp               ; jump to rkill if he is damaged
rclr     mov    rc,>200                ; slow forward core-clear
         jmp    set,#1010
initrp   dat    #0-2353,#re-rp+1+space
rc       dat    <2667,#1               ; imp-killing, plus djn-stream disrupt
re       dat    <2667,#re-rb+1+space   ; for quick restore of partner
         
st       mov #0,rclr+boot+space+200
         mov #100,rclr+boot+200
         spl 1                         ; create 14 processes
         spl 1
         mov -1,0
         spl 1
         spl s2
         mov <copyf,<copyt1            ; copy and start partners
         jmp set+space+boot
s2       mov @copyf,<copyt2
         jmp set+boot
         end st

The other lines were saved in the kill-and-restore code.  'rb' is post-
incremented to dat-bomb partner, then pre-decremented to restore partner.
This saves either having two pointers, or having to reset rb before
restoring, which is what the '88 version did.  Unfortunately, there
needs to be a one-line delay between dat-bomb and restore to allow time for
any spl-created processes in partner to die, so I didn't actually
save a line there but was able to change it to short dat-bombing
line.

Since rb is incremented and decremented by the same amount, I don't have
to reset it after restore as was necessary under '88.  _Unfortunately_
the old 'in-register' vs. 'in-memory' thing caught me here, because
when rb itself is copied to partner it is 'pre-decrement', therefore
incorrect, and an extra line is taken up correcting rb in partner.
I can't see any way around this.  If rb is in the code, it will
always be copied incorrectly and if it is out of the code, it has to
be set before being used - either way a line is needed.

Bunker uses a very non-agressive core-clear for attack.  A faster
attack would surely be more successful, since it frequently resurrects
partners many times before yielding to a fatal combination attack.
It is also succeptible to a single decrement in the monitoring loop
which will cause both partners to go into kill mode, first one there
kills the other and if its the wrong one, all is lost.

One problem is that every time a line is changed, you have to re-figure
the b-operand sum.  Just run bunker alone and see what he comes up with.

I haven't given up on Bunker.  It's just too interesting and too 
much fun to watch.  But there's that cmp-scanner that can quickly
id a stone opponent to work on :-)

Paul Kline
pk6811s@acad.drake.edu

PS.  I grovel before Stefan's analysis of the White Knight problem. :-)

However, Michael's remark that Smite doesn't address the problem of
scanning itself doesn't compute.  It would take 8000 cycles for
Smite White to scan itself, but would surely find one of Challenge1's
bombs first :-)